package com.hda.adbt;

import java.awt.Point;
import java.util.Stack;
import java.util.Vector;

import com.hda.adbt.pointfunc.PointOperations;

public class ConvexHull 
{
	Stack<PointOperations> points = new Stack<PointOperations>();
	Vector<PointOperations> p = new Vector<PointOperations>();
	PointOperations pUse = new PointOperations();
	boolean useX = false;
	
	public boolean createCHfromPoints(Vector<Point> pol)
	{
		Vector<PointOperations> pov = new Vector<PointOperations>();
		for (int i = 0; i < pol.size(); i++)
		{
			pov.add(new PointOperations(pol.elementAt(i)));
		}
		return createCH(pov);
	}
	
	private void printPoints()
	{
		System.out.print("p = ");
		for (int i = 0; i < p.size(); i++)
			System.out.print(p.get(i).toString()+", ");
		System.out.println();

		System.out.print("points = ");
		for (int i = 0; i < points.size(); i++)
			System.out.print(points.get(i).toString()+", ");
		System.out.println();
	}
	
	public boolean createCH(Vector<PointOperations> pol) 
	{
		p = pol;
		// Are there enough points?
		if(p.size() < 3) return false;
		
		int ind = 0;
		
		for(int i=0; i < p.size(); i++)
		{
			if( i == 0 ) pUse = p.elementAt(i);
			if (p.elementAt(i).isLower(pUse))
			{
				pUse = p.elementAt(i);
				ind = i;
			}
		}

		//if (!movePointToIndex(0, pUse)) return false;
		exchange(0,ind);

		sort();
		// P0 always part of CV
		points.push(p.elementAt(0));
		points.push(p.elementAt(1));
		points.push(p.elementAt(2));
		
		printPoints();
		
		for (int k = 3; k < p.size(); k++)
		{
			PointOperations pt = points.peek();
			PointOperations ptn = points.get(points.size()-2);
			
			//System.out.println("k="+ p.elementAt(k).toString());
			//System.out.println("pt="+pt.toString());
			//System.out.println("ptn="+ptn.toString());
			
			//if (!p.elementAt(k).isRightOf(pt, ptn))
			if(calculateArea(ptn, pt, p.elementAt(k)) >= 0 )
			{
				System.out.println("Push: "+p.elementAt(k).toString());
				points.push(p.elementAt(k));
				continue;
			}
			// This should be executed similar to an else branch
			//while (p.elementAt(k).isRightOf(pt, ptn))
			while(calculateArea(ptn, pt, p.elementAt(k)) <= 0 )
			{
				System.out.println("Pop: "+points.peek().toString()+" Element k: "+p.elementAt(k).toString());
				points.pop();
				pt = points.peek();
				ptn = points.get(points.size()-2);
			}
			--k;

			System.out.println();
		}
		
		return false;
	}
	
	private void sort()
	{
		quicksort(1, p.size()-1);
		//bubblesort();
	}
	
	private void quicksort(int lo, int hi)
	{
		int i = lo, j = hi;
		PointOperations q = p.elementAt((lo+hi) / 2);
		
		while (i <= j)
		{
			//while (p.elementAt(i).isLess(q)) i++;
			while(calculateArea(pUse, q, p.elementAt(i)) < 0) i++;
			//while (q.isLess(p.elementAt(j))) j--;
			while(calculateArea(pUse, p.elementAt(j), q) < 0) j--;
            if (i<=j) exchange(i++, j--);
		}
		
		if (lo<j) quicksort(lo, j);
        if (i<hi) quicksort(i, hi);
	}
	
	private void bubblesort()
	{
		boolean swapped = true;
		int j = 0;
		
		while (swapped)
		{
			swapped = false;
			j++;
			for (int i = 1; i < p.size()-j ; i++)
			{
				double res = calculateArea(pUse, p.elementAt(i), p.elementAt(i+1));
				if (res < 0 )//p.elementAt(i).isLess(p.elementAt(i+1)))
				{
					//System.out.println("Punkt i: "+p.elementAt(i).toString()+"Punkt i+1: "+p.elementAt(i+1).toString()+" res: "+res);
					exchange(i, i+1);
					swapped = true;
				}
			}
		}
		printPoints();
	}
	
	private int calculateArea(PointOperations p1, PointOperations p2, PointOperations p3)
	{
		return ( (p2.x - p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y) );
	}
	
	private void exchange(int a, int b)
	{
		PointOperations tmp = p.elementAt(a);
		p.set(a, p.elementAt(b));
		p.set(b, tmp);
	}


	private boolean movePointToIndex(int index, PointOperations poi)
	{
		// TODO: raise exception if point does not exist!
		if (!p.contains(poi)) return false;
		PointOperations pot = p.elementAt(index);

		for(int i = 0; i < p.size(); i++)
		{
			// find index of lowest point and move it to index 0
			if(p.elementAt(i).x == poi.x && p.elementAt(i).y == poi.y)//p.elementAt(i).fits(pot))
			{
				p.set(index, p.elementAt(i));
				p.set(i, pot);
				return true;
			}
		}
		return false;
	}
	
	public void printCH()
	{
		System.out.println("Polygon: \n");
		for(int j=0; j < p.size(); j++)
		{
			System.out.println(p.elementAt(j)+" ");
		}
		System.out.println("\nStack: \n");
		for(int i=0; i < points.size(); i++)
		{
			System.out.println(points.elementAt(i)+" ");
		}
	}
}

